A symmetric cryptosystem is a method of encrypting (also called encoding) and decrypting (also called decoding) information involving the use of an identical secret key for both the encryption and decryption. The Rijndael algorithm, which is a substitution linear transformation block cipher, can support a symmetric cryptosystem. The Rijndael algorithm processes plain text in blocks of 128, 192, or 256 bits, and uses cipher keys of length 128, 192, or 256 bits. The Advanced Encryption Standard (AES) is a standardized implementation of the Rijndael algorithm used for securing sensitive material. The AES is defined by the United States' National Institute of Standards and Technology in Federal Information Processing Standards Publication 197, available at <http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf; retrieved Jan. 3, 2006>, incorporated herein by reference in its entirety.
The AES algorithm, as currently defined, processes data in blocks sizes of 128 bits. Data block size is represented by Nb, where Nb is the number of 32-bit words in a block. Thus, for 128-bit blocks, Nb=4. The length of the cipher key used is represented by Nk, where Nk is the number of 32-bit words in the cipher key. The AES standard, as currently defined, allows use of cipher keys with lengths of 128 bits (wherein Nk=4), 192 bits (Nk=6), or 256 bits (Nk=8). A particular implementation of the AES standard must support at least one of the standard cipher key lengths. A block of unencrypted data (i.e., plaintext) is transformed over a series of rounds, where the number of rounds, represented by Nr, is dependent on the length of the cipher key. There are 10 rounds when using 128-bit keys, 12 when using 192-bit keys, and 14 when using 256-bit keys. The AES standard recognizes that, in the future, the specific values for key length, block size, and number of rounds are subject to change.
The working data block, or intermediate cipher result, of AES encryption and decryption is known as the State, and can be represented as a rectangular array of bytes having four rows and four columns of 8-bit bytes (for a total of 128 bits). The bytes can be viewed as finite field elements. They can be added and multiplied, but those operations are different from those used for numbers. For example, both addition and its inverse are implemented by performing an exclusive-OR (XOR) operation, while multiplication involves modulo reduction. Unless otherwise noted, references herein to addition mean the performance of an XOR operation. Similarly, adders referenced herein perform an XOR operation on the quantities added. Encryption and decryption start with the copying of a block of data into the State array, where the bytes will be transformed over the requisite number of rounds, and then the State's final value will be copied to a corresponding output block.
The AES algorithm takes the cipher key, and performs a key expansion routine to generate a key schedule with a total of Nb(Nr+1) 32-bit words, which are used for both encryption and decryption. Each round of encryption or decryption uses a different set of Nb words from the key schedule. The first Nk words, equivalent to one cipher key length, of the expanded key schedule are filled with the cipher key. Every subsequent word, w[i], is equal to the XOR of the previous word, i.e., w[i−1], and the word Nk positions earlier, i.e., w[i−Nk]. For words in positions that are a multiple of Nk, prior to the XOR with w[i−Nk], a transformation is applied to w[i−1], followed by an XOR with a 32-bit round constant, Rcon[i]. The above transformation consists of a cyclic shift (RotWord( )) of the bytes in the word, followed by the application of a table lookup substitution (SubWord( )) to all four bytes of the word. The key expansion routine for 256-bit cipher keys (Nk=8) is slightly different, wherein the SubWord( ) transform is also applied to w[i−1] prior to the XOR with w[i−Nk] when [i−4] is a multiple of Nk.
For both its encryption and decryption, the AES algorithm uses a round function that is composed of four different byte-oriented transformations: (1) byte substitution using a substitution table (S-box), (2) shifting rows of the State array by different offsets, (3) mixing the data within each column of the State array, and (4) adding a round key to the State.
Encryption starts with an initial stage in which an initial round key is added to the State. This initial stage is sometimes referred to as round zero. The initial stage is then followed by Nr rounds of transformations. The first Nr−1 rounds include the above four transformations, represented as SubBytes( ), ShiftRows( ), MixColumns( ), and AddRoundKey( ), respectively. The final round, i.e., round Nr, does not include the MixColumns( ) transformation. After the final round, the State, containing encrypted data (i.e., ciphertext), is copied to the output. Each round uses a new 128-bit round key, which is derived from the cipher key using a set of transformations as described above. Thus, a total of Nr+1 round keys are used in encrypting information under the AES standard. The size of the round key is dependent on the size of the State, which is 128 bits under the AES standard, and which differs from the size of the cipher key if, for example, the 192-bit or 256-bit cipher keys are used. If, for example, a 256-bit cipher key is used, then the key schedule is expanded until there are 60 words in the schedule, for each of the four words used as a round keys in the initial stage and the 14 rounds of encryption or decryption (i.e., 60=4*(1+14)).
Straightforward AES decryption uses the inverse transformations of the encryption transformations. The decryption algorithm involves the following sequence of transformations: (1) InvShiftRows( ), (2) InvSubBytes( ), (3) AddRoundKey( ) (since XOR is its own inverse), and (4) InvMixColumns( ). Like encryption, decryption proceeds for an initial stage followed by Nr rounds using the same Nr+1 round keys used for encryption; however, the round keys are used in reverse order, starting with the final round key of the key schedule, stepping backwards through the expanded key schedule, and ending with the initial round key. The expanded key schedule is created in the same way as in the encryption process. Decryption starts with the copying of a block of encrypted data (i.e., ciphertext) to the State and the addition of the final round key of the key schedule to the State. This is followed by Nr−1 identical rounds of transformation, which include the above four inverse transformations, and wherein the AddRoundKey( ) transformation steps backwards through the key schedule. The final round (round Nr) does not include the InvMixColumns( ) transformation.
The AES standard also provides an equivalent decryption process that allows a reordering of the inverse procedures based on commutative and distributive properties of combinations of the procedures, and which is particularly beneficial for systems that perform both encryption and decryption. The equivalent decryption process requires the transformation of the round keys for rounds 1 to Nr−1 using an InvMixColumns( ) procedure, which can be accomplished by using the expanded key schedule and transforming the appropriate round keys therein. The equivalent decryption process starts with the addition of the final round key, i.e., the last Nb words of the key expansion schedule, followed by Nr−1 identical rounds of InvSubBytes( ), InvShiftRows( ), InvMixColumns( ), and AddRoundKey( ) transformations, respectively, stepping backwards through the key expansion schedule. The final round does not include the InvMixColumns( ) transformation for the State. After the final round, the State, containing deciphered data (i.e., plaintext), is copied to the output.
Current approaches for implementing the AES-Rijndael algorithm in semiconductor devices typically use Nk·(Nr+1) registers to store the entire key expansion table on chip. This storage requires an undesirably large number of gates and consequent large chip area.